1. Field of the Invention
This invention relates to transaction systems, and more specifically to secure transaction systems involving tamper-resistant devices.
2. Description of Prior Art
Reference is hereby made to P.C.T. publication WO 89/08957, E.P.O. filing 89905483.7, and U.S. Pat. No. 4,987,593 filed Mar. 16, 1988, titled xe2x80x9cOne-Show Blind Signature Systemsxe2x80x9d by Chaum, which are incorporated herein by reference. Reference is also hereby made to E.P.O. filing 90200207.0 and U.S. Pat. No. 5,131,039 filed Jan. 29, 1990, titled xe2x80x9cOptionally moderated transaction systemsxe2x80x9d by Chaum, which are incorporated herein by reference. Reference is also hereby made to U.S. Pat. No. 4,914,698 filed Jul. 24, 1989, titled xe2x80x9cOne-show blind signature systemsxe2x80x9d by Chaum and to U.S. Pat. No. 5,276,736, filed Jul. 13, 1992, titled xe2x80x9cOptionally moderated transaction systemsxe2x80x9d by Chaum, which are incorporated herein by reference.
A basic technique for xe2x80x9cendorsingxe2x80x9d a public key digital signature was disclosed in the first above included reference and a related paper presented at Crypto ""88. This technique was used in the second above included reference and also in other subsequent publications, such as, for example, U.S. Pat. No. 5,016,274 by Micali et al. related to a paper presented at Crypto ""89 and CWI technical Report CS-R9035.
Endorsement schemes are simply one-time signature schemes where the authentication of the public key that is always needed in one time signature schemes is done using the very well know technique of a public key certificate.
Three efficiency improvements for the endorsement function, compared to that first disclosed in the first above included reference, are known in the prior art. The first two pertain to one-time signature schemes and the third improves the true public key digital signatures.
The first two improvements were made in the context of the well-know original one-time signatures called xe2x80x9cLamportxe2x80x9d signatures that are disclosed and attributed to Lamport in xe2x80x9cNew directions in cryptography,xe2x80x9d IEEE Transaction on Information Theory, pp. 644, 654, 1976, and are also subsequently described by Lamport in SRI technical report CSL 98. Lamport signatures simply authenticate, as a public key, the output of a public one-way function on a list of secret values, later release of a subset of the secret values allows anyone to confirm both that they correspond to the authenticated list and the message signed by being encoded in the choice of subset.
The first improvement is believed disclosed at least in IBM Technical Disclosure Bulletin, vol. 28, no. 2, July 1985, pp. 603-604, titled xe2x80x9cMatrix digital signature for use with the data encryption algorithmxe2x80x9d and in the Proceedings of Crypto ""87 by Merkle in the context of Lamport signatures and was subsequently incorporated in the second above included reference by Chaum. This first improvement reduces the size of the original list of secret inputs to the one-way function. Instead of simply basing the signature on single independent applications of one-way functions, the functions are composed or xe2x80x9cchainedxe2x80x9d so that the output of the previous function application in the chain serves as the input of the next function application. Each chain can be thought of as representing one digit of the numeric message signed by the one-time scheme. The radix is one plug the length of the chain, with the original Lamport signatures having radix 2. This first improvement results in economy of storage and transmission, at the expense of an increase in computation.
The second efficiency improvement was also disclosed by Merkle, as cited above. It applies techniques, believed known in the coding art, that reduce the number of xe2x80x9ccontrolxe2x80x9d digits needed. These digits prevent a signature from being changed into a signature on a different message. The previous disclosures cited used one control digit per message digit, with the control digit representing the additive inverse of the message digit. The improvement works essentially by having only a few control digits that represent the additive inverse of the sum of the message digits. Accordingly, the number of control digits is reduced from being linear in the number of message digits to being only logarithmic.
The third improvement applies to certain public key digital signature schemes. It was disclosed first in U.S. Pat. No. 4,949,380, in a paper presented at Crypto ""89, PCT publication US89/04662, and EPO application 89912051.3, all substantially the same and all by Chaum. This improvement allows plural public key signatures to be xe2x80x9cintermingledxe2x80x9d in the space taken by one, so long as they are made with coprime public exponents. They can be signed in the intermingled form, stored in that form, and later separated for showing. This technique also gives economy of storage (and communication), although potentially at the expense of extra computation.
One commercially interesting use of endorsement schemes appears to be in the area of xe2x80x9cprepaid cards.xe2x80x9d
A prepaid smart card contains stored value which the person holding it can spend at retail points of payment. After accepting stored value from cards, retailers are periodically reimbursed with actual money by system providers. A system provider receives money in advance from people and stores corresponding value onto their cards. During each of these three kinds of transactions, secured data representing value is exchanged for actual money or for goods and services. Telephone cards used in France and elsewhere are probably the best known prepaid smart cards (though some phone cards use optical or magnetic techniques). National prepaid systems today typically aim to combine public telephones, merchants, vending, and public transportation. Automatic collection of road tolls may also be included soon.
Growth in the prepaid smart card market appears to be rapid. For instance, at the time of this application it is believed that national prepaid chipcard schemes are rolling out in Denmark, under construction in Portugal, and planned in Belgium, Spain, and France. The MAC network, believed the largest ATM network in the United States, has announced its entry, and systems are apparently already operational in South Africa and Switzerland.
In schemes based solely on conventional cryptography used by cards, secured modules (sometimes called SAM""s) are needed at every point of payment. The reason is that transactions are consummated without communication with external sites, to keep transaction costs comensurate with the low-value of payments, and that conventional cryptographic authentication requires the communicants to share a common secret. Each secure module is believed to require the ability to develop secret keys of all cards, which gives some problems. If the cards of multiple system providers are to be accepted at the same point of payment, all the points of payment must have secured modules containing keys of every provider. This is believed to mean either a mutually trusted module containing the keys of multiple providers, which might be hard to achieve, or one module per provider, which becomes impractical as the number of providers grows. Furthermore, in any such system, if a module is penetrated, not only may significant retailer fraud be facilitated, but the entire card base may be compromised.
Endorsement schemes avoid these problems since they do not require such secured modules. Equipment at points of payment needs no secret keys, only public ones, in order to authenticate the endorsements, which act like guaranteed checks filled in with all the relevant details. These same endorsements can later be verified by the system provider for reimbursement. (While these systems allow full end-to-end verification, tamper-resistant aggregators can always be used for truncation.) They also allow the cards of any number of issuers to be accepted at all retailers; retailers cannot cheat issuers, and issuers cannot cheat each other.
The size of the chip in the card is of substantial practical importance in such systems. With a given technology, the more storage the more the chips cost to produce and the bigger they are. It is believed that in the industry larger chips are also thought to mean higher card production costs, and less reliable and durable cards. Cards announced so far for such national prepaid systems use only conventional cryptographic authentication and have only about one kilobyte of nonvolatile storage. For endorsement techniques to be competitive, it is believed important that they can be fit into the same chips. Prior art techniques do not allow enough endorsements to be stored in such chips.
Furthermore, it is believed that ordinary credit card and/or debit card transactions consummated using a smart card would benefit from the additional security of an off-line public key endorsement of their transaction details.
Transaction systems using a tamper-resistant device are well known. Usually the tamper-resistant device has the form of a smart card. Most smart card transaction systems are targeted to financial transactions, but many other transaction such as access control are in use. In most smart card systems the smart card has one or more secret keys specific to that smart card, while each terminal has one or more xe2x80x98master keysxe2x80x99 in a tamper-resistant device which allow the terminal to derive the secret keys of the smart cards. Once both parties in the transaction have a secret key in common, the security and authenticity of the transaction can be ensured using traditional cryptographic methods. The xe2x80x98master keysxe2x80x99 in the terminal are a weak point in these systems, as any attack which succeeds in getting these keys out of a terminal leads to a catastrophic breakdown of the security. Methods of solving this problem usually involve the application of some kind of public key cryptography. Using smart cards with a public key cryptographic capability is one solution, but such smart cards are more expensive than simple ones.
During a transaction a smart card will typically update one or more locations in non-volatile memory, which could for example consist of EEPROM. Present smart cards are sometimes vulnerable to interruptions during the update which leads to security and reliability problems. Any faults in the non-volatile memory often lead to wrongful transaction processing. Another weakness of smart cards using EEPROM memory is an attack in which the smart card is irradiated using ultraviolet (UV) light. It is known that this influences the data stored in the EEPROM, and might thus be used to attack the security of the system. Some types of transactions require several items in non-volatile memory to be modified simultaneously, a requirement which is not supported in current smart cards.
The different actions which make up a transaction are mostly not bound together by cryptographic means, making it harder to provide adequate security for complex transactions and often necessitating the use of specialized actions. Financial transaction system smart cards which are used for payment purposes typically subtract the amount of the payment from the internally held balance before giving out the cryptographic proof to the terminal that the payment has been made. Any interruption in the time between this update and the sending of the proof can lead to a loss of money, unless special recovery procedures are used.
Most smart cards willingly reveal a lot of information, often including a unique card identity number, directory structure etc. Although this information is usually not directly relevant to the security of the application, it can provide additional information to the terminal which might be used to invade the privacy of the owner of the smart card.
The tamper resistance of smart cards is typically used to allow the smart card to execute processes using some secret information (e.g. secret cryptographic keys), and care is taken in the design of transaction systems that the smart card does not reveal any of the secret information to the terminal. However, a terminal might perform many more measurements then just looking at the data that is sent by the card; it is our belief that many existing systems are vulnerable to an attack which uses these additional measurements.
The recently published specifications for the EMV system xe2x80x9cIntegrated Circuit Card Specifications for Payment Systems: Part 1, Electromechanical Characteristics, Logical Interface, and Transmission Protocols, version 1.1, Part 2, Data Elements and Commands, version 1.1, and Part 3, Transaction Processing, version 1.0xe2x80x9d all data Oct. 31, 1994 by Europay International S.A., MasterCard International Incorporated, and Visa International Service Association define a system designed for credit card applications. They allow off-line processing of some credit card transactions. The specifications seem to envision a setting where the terminal does not have access to any secret keys, the specified off-line transactions do not include any means for the terminal to verify the authenticity of the card and the transaction data in this setting. Furthermore, the specifications seem not to take full advantage of the capabilities of a smart card. The EMV specifications are envisioned to be used for several types of financial transactions, including credit card payments, direct debiting of the user""s account, pre-paid payments where the money resides in the card etc. The specifications do not address the underlying similarity in structure for all of these applications.
For some types of transactions, and specifically for financial ones, there is also a clearing process. In this process the terminals send information regarding the money they collected to the acquirer and/or issuer. Current systems rely on either having the terminal forward full transaction information to the acquirer, or having a tamper-resistant device (often called SAM) in the terminal to do the truncation: the SAM accepts the transaction data, verifies them, and keeps track of the necessary totals. This allows some or all of the transaction data to be discarded, the necessary clearing information is forwarded by the SAM to the acquirer and/or issuer and authenticated using some cryptographic scheme. Forwarding all transaction information can be expensive and cumbersome, while having SAMs in terminals can be expensive. When a single terminal has to deal with many different issuers/acquirers, the terminal either needs separate SAMs for each of the issuers/acquirers, which is expensive, or a single SAM which is trusted by all the issuers/acquirers, which leads to organizational difficulties.
Accordingly, it is an object of the present invention to:
provide a secure, flexible, efficient and reliable multi-purpose transaction system;
provide a secure and efficient authentication capability for smart cards, which does not rely on a capability of the smart card to performing public key cryptographic computations in an adequate fashion;
provide a secure atomic update of the non-volatile memory in smart cards for one or more modifications to the data in the memory, even under arbitrary interruptions and some physical attacks;
provide proper cryptographic proofs and verifications that the different actions that make up a transaction are kept together and executed in order;
prevent the smart card from revealing any information to terminals that do not have access to the appropriate keys;
prevent the smart card from revealing any information in addition to the information communicated as part of the transaction, through any external behaviour;
provide clearing methods and systems that do not communicate all the transaction data, without the use of one or more tamper-resistant devices in the terminal;
protect the terminals interest in off-line EMV transactions by adding a public key based digital authentication to the transaction;
provide a general transaction structure that can be used for credit card transactions, pre-paid transactions, direct debit transactions etc.; and
allow efficient, economical, and practical apparatus and methods fulfilling the other objects of the invention.